{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Gap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #bucket-sort #radix-sort #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #桶排序 #基数排序 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumGap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大间距"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个无序的数组&nbsp;<code>nums</code>，返回 <em>数组在排序之后，相邻元素之间最大的差值</em> 。如果数组元素个数小于 2，则返回 <code>0</code> 。</p>\n",
    "\n",
    "<p>您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [3,6,9,1]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong> 排序后的数组是 [1,3,6,9]<strong><em>, </em></strong>其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [10]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong> 数组元素个数小于 2，因此返回 0。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-gap](https://leetcode.cn/problems/maximum-gap/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-gap](https://leetcode.cn/problems/maximum-gap/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,6,9,1]', '[10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        sz = len(nums)\n",
    "        if sz < 2:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        result = 0\n",
    "        for i in range(sz - 1):\n",
    "            a = nums[i]\n",
    "            b = nums[i + 1]\n",
    "            c = b - a\n",
    "            result = max(result, c)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def maximumGap(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 获取数字的个数\n",
    "        count = len(nums)\n",
    "        # 如果小于两个数字，则根据题意返回0\n",
    "        if count < 2:\n",
    "            return 0\n",
    "        # 确定所有数的范围，寻找最值和最小值\n",
    "        maxnum, minnum = max(nums), min(nums)\n",
    "        # 计算数与数之间的平均距离（例如有10个数字，则一共有9个区间，平均的区间差为（最大值-最小值/9）向上取整）\n",
    "        gap = math.ceil((maxnum - minnum) / (count - 1))\n",
    "        # 如果gap\n",
    "        if gap == 0:\n",
    "            return 0\n",
    "        size = int((maxnum - minnum) / gap) + 1\n",
    "        bucketmin, bucketmax = [sys.maxsize] * size, [-sys.maxsize] * size\n",
    "        for i in range(count):\n",
    "            index = int((nums[i] - minnum) / gap)\n",
    "            bucketmin[index] = min(bucketmin[index], nums[i])\n",
    "            bucketmax[index] = max(bucketmax[index], nums[i])\n",
    "        premax, maxgap = bucketmax[0], 0\n",
    "        for i in range(1, size):\n",
    "            if bucketmin[i] != sys.maxsize:\n",
    "                maxgap = max(maxgap, bucketmin[i] - premax)\n",
    "                premax = bucketmax[i]\n",
    "        return maxgap\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        buckets = [None for i in range(n)]\n",
    "        min_value = min(nums)\n",
    "        max_value = max(nums)\n",
    "        r = (max_value - min_value + 1) / n\n",
    "        for num in nums:\n",
    "            id_bucket = math.ceil((num - min_value + 1) / r) - 1\n",
    "            if buckets[id_bucket] is None:\n",
    "                buckets[id_bucket] = (num, num)\n",
    "            else:\n",
    "                buckets[id_bucket] = (min(num, buckets[id_bucket][0]), max(num, buckets[id_bucket][1]))\n",
    "        last_bucket = None\n",
    "        max_gap = 0\n",
    "        for bucket in buckets:\n",
    "            if bucket == None:\n",
    "                continue\n",
    "            if last_bucket != None:\n",
    "                max_gap = max(max_gap, bucket[0] - last_bucket[1])\n",
    "            last_bucket = bucket\n",
    "        return max_gap\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n <=1:\n",
    "            return 0\n",
    "        maxN = minN = nums[0]\n",
    "        for num in nums:\n",
    "            if num < minN:\n",
    "                minN = num\n",
    "            if num > maxN:\n",
    "                maxN = num\n",
    "        if maxN - minN <=1:\n",
    "            return maxN - minN\n",
    "        b = (maxN - minN) / n\n",
    "        k = int((maxN - minN) / b) + 1\n",
    "        bucket_mins = [None]*k\n",
    "        bucket_maxs = [None]*k\n",
    "        for num in nums:\n",
    "            index = int((num - minN) / b)\n",
    "            if bucket_maxs[index] == None:\n",
    "                bucket_maxs[index] = num\n",
    "                bucket_mins[index] = num\n",
    "            else:\n",
    "                if bucket_maxs[index] < num:\n",
    "                    bucket_maxs[index] = num\n",
    "                if bucket_mins[index] > num:\n",
    "                    bucket_mins[index] = num\n",
    "        preMax = None\n",
    "        max_gap = 0\n",
    "        for i in range (k):\n",
    "            if bucket_mins[i]!=None:\n",
    "                if preMax != None and bucket_mins[i] - preMax > max_gap:\n",
    "                    max_gap = bucket_mins[i] - preMax\n",
    "                preMax = bucket_maxs[i]\n",
    "        return max_gap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ln = len(nums)\n",
    "        if ln < 2:\n",
    "            return 0\n",
    "        maxn = max(nums)\n",
    "        minn = min(nums)\n",
    "        nums = set(nums)\n",
    "        ln = len(nums)\n",
    "        if ln < 2:\n",
    "            return 0\n",
    "        gap = (maxn - minn)//(ln-1)\n",
    "        if gap==0:\n",
    "            return 0\n",
    "        pcs = (maxn-minn)//gap\n",
    "        buckets = [[] for x in range(pcs+1)]\n",
    "        for x in nums:\n",
    "            index = (x-minn)//gap\n",
    "            if len(buckets[index]) == 0:\n",
    "                buckets[index].append(x)\n",
    "            elif len(buckets[index]) == 1:\n",
    "                buckets[index].append(x)\n",
    "                buckets[index].sort()\n",
    "            else:\n",
    "                buckets[index][0] = min(buckets[index][0],x)\n",
    "                buckets[index][1] = max(buckets[index][1],x)\n",
    "        i = 0\n",
    "        while len(buckets[i])==0:\n",
    "            i+=1\n",
    "        g = 0\n",
    "        last = buckets[i][-1]\n",
    "        while i<len(buckets):\n",
    "            if len(buckets[i]) == 0:\n",
    "                i += 1\n",
    "                continue\n",
    "            g = max(g,buckets[i][0]-last)\n",
    "            last = buckets[i][-1]\n",
    "            i+=1\n",
    "        return g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    def maximumGap(self, nums):\n",
    "        l = len(nums)\n",
    "        if l < 2:\n",
    "            return 0        \n",
    "        polar = nums[0]\n",
    "        lgaps = []\n",
    "        rgaps = []\n",
    "        for num in nums[1:]:\n",
    "            gap = num - polar\n",
    "            if gap > 0:\n",
    "                rgaps.append(gap)\n",
    "            elif gap < 0:\n",
    "                lgaps.append(-gap)\n",
    "        results = []\n",
    "        if len(rgaps) > 0:\n",
    "            results.append(min(rgaps))\n",
    "            results.append(self.maximumGap(rgaps))\n",
    "        if len(lgaps) > 0:\n",
    "            results.append(min(lgaps))\n",
    "            results.append(self.maximumGap(lgaps))\n",
    "        return max(results) if len(results) > 0 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    def maximumGap(self, nums):\n",
    "        l = len(nums)\n",
    "        if l < 2:\n",
    "            return 0\n",
    "        if l == 2:\n",
    "            return nums[1] - nums[0] if nums[1] > nums[0] else nums[0] - nums[1]\n",
    "        polar = nums[0]\n",
    "        left = []\n",
    "        right = []\n",
    "        lgaps = []\n",
    "        rgaps = []\n",
    "        for num in nums:\n",
    "            gap = num - polar\n",
    "            if gap > 0:\n",
    "                right.append(num)\n",
    "                rgaps.append(gap)\n",
    "            elif gap < 0:\n",
    "                left.append(num)\n",
    "                lgaps.append(-gap)\n",
    "        options = [self.maximumGap(left), self.maximumGap(right)]\n",
    "        if len(lgaps) > 0:\n",
    "            options.append(min(lgaps))\n",
    "        if len(rgaps) > 0:\n",
    "            options.append(min(rgaps))\n",
    "        return max(options)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    def maximumGap(self, nums):\n",
    "        l = len(nums)\n",
    "        if l < 2:\n",
    "            return 0\n",
    "        if l == 2:\n",
    "            return nums[1] - nums[0] if nums[1] > nums[0] else nums[0] - nums[1]\n",
    "        polar = nums[0]\n",
    "        left = []\n",
    "        right = []\n",
    "        lgaps = []\n",
    "        rgaps = []\n",
    "        for num in nums:\n",
    "            gap = num - polar\n",
    "            if gap > 0:\n",
    "                right.append(num)\n",
    "                rgaps.append(gap)\n",
    "            elif gap < 0:\n",
    "                left.append(num)\n",
    "                lgaps.append(-gap)\n",
    "        options = []\n",
    "        if len(lgaps) > 0:\n",
    "            options.append(min(lgaps))\n",
    "            options.append(self.maximumGap(left))\n",
    "        if len(rgaps) > 0:\n",
    "            options.append(min(rgaps))\n",
    "            options.append(self.maximumGap(right))\n",
    "        return 0 if len(options) == 0  else max(options)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums) < 2:\n",
    "            return 0\n",
    "\n",
    "        numDic = {}\n",
    "        uniqNums = []\n",
    "        mini, maxi = nums[0], nums[0]\n",
    "        for n in nums:\n",
    "            if n in numDic:\n",
    "                continue\n",
    "            uniqNums.append(n)\n",
    "            numDic[n] = 1\n",
    "            if n < mini:\n",
    "                mini = n\n",
    "            if n > maxi:\n",
    "                maxi = n\n",
    "\n",
    "        numCount = len(uniqNums)\n",
    "        if numCount < 2:\n",
    "            return 0\n",
    "        elif numCount == 2:\n",
    "            return abs(uniqNums[1] - uniqNums[0])\n",
    "        elif numCount == (maxi - mini + 1):\n",
    "            return 1\n",
    "\n",
    "        ranges = {}\n",
    "        rangeWidth = (maxi - mini + 1) // (numCount + 1)\n",
    "        for num in uniqNums:\n",
    "            i = (num - mini) // rangeWidth \n",
    "            if i >= numCount:\n",
    "                ranges[numCount] = 1\n",
    "            else:\n",
    "                ranges[i] = 1\n",
    "\n",
    "        widestEmptyRange = []\n",
    "        maxWidth, i = 0, 0\n",
    "        while i < numCount:\n",
    "            if i in ranges:\n",
    "                i += 1\n",
    "                continue\n",
    "            j = i + 1\n",
    "            width = 1\n",
    "            while j < numCount + 1:\n",
    "                if j not in ranges:\n",
    "                    width += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    break\n",
    "            if width > maxWidth:\n",
    "                widestEmptyRange = [[i, j - 1]]\n",
    "                maxWidth = width\n",
    "            elif width == maxWidth:\n",
    "                widestEmptyRange.append([i, j - 1])\n",
    "            i = j\n",
    "\n",
    "        gap = 0\n",
    "        for r in widestEmptyRange:\n",
    "            offsetLow = mini + r[0] * rangeWidth\n",
    "            offsetHigh = mini + (r[1] + 1) * rangeWidth - 1\n",
    "            while True:\n",
    "                if offsetLow in numDic and offsetHigh in numDic:\n",
    "                    break\n",
    "                else:\n",
    "                    if offsetLow not in numDic:\n",
    "                        offsetLow -= 1\n",
    "                    if offsetHigh not in numDic:\n",
    "                        offsetHigh += 1\n",
    "                \n",
    "            if offsetHigh - offsetLow > gap:\n",
    "                gap = offsetHigh - offsetLow\n",
    "\n",
    "        return gap\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    def maximumGap(self, nums):\n",
    "        l = len(nums)\n",
    "        if l < 2:\n",
    "            return 0\n",
    "        n1 = self.createNode(nums[0])\n",
    "        n2 = self.createNode(nums[1])\n",
    "        if n1['v'] > n2['v']:\n",
    "            n1['l'] = n2\n",
    "            n2['r'] = n1\n",
    "            self.queue = [n1]\n",
    "            self.leftBoundary = n2\n",
    "            self.rightBoundary = n1\n",
    "        else:\n",
    "            n1['r'] = n2\n",
    "            n2['l'] = n1\n",
    "            self.queue = [n2]\n",
    "            self.leftBoundary = n1\n",
    "            self.rightBoundary = n2\n",
    "        self.pending = []\n",
    "        for num in nums[2:]:\n",
    "            if self.updateQueueIfNodeInMaxGap(num):\n",
    "                self.rebuildQueue()\n",
    "        right = self.queue.pop()\n",
    "        left = right['l']\n",
    "        return right['v'] - left['v']\n",
    "\n",
    "    def updateQueueIfNodeInMaxGap(self, num):\n",
    "        if num > self.rightBoundary['v']:\n",
    "            node = self.createNode(num, self.rightBoundary)\n",
    "            self.rightBoundary['r'] = node\n",
    "            self.rightBoundary = node\n",
    "            self.addNode(node)\n",
    "            return False\n",
    "        elif num < self.leftBoundary['v']:\n",
    "            node = self.createNode(num, None, self.leftBoundary)\n",
    "            self.leftBoundary['l'] = node\n",
    "            self.addNode(self.leftBoundary)\n",
    "            self.leftBoundary = node\n",
    "            return False\n",
    "        \n",
    "        right = self.queue.pop()\n",
    "        left = right['l']\n",
    "        if num > left['v'] and num < right['v']:\n",
    "            node = self.createNode(num, left, right)\n",
    "            right['l'] = left['r'] = node\n",
    "            self.addNode(right)\n",
    "            self.addNode(node)\n",
    "            return True\n",
    "        else:\n",
    "            self.pending.append(num)\n",
    "            self.queue.append(right)\n",
    "            return False\n",
    "    \n",
    "    def addNode(self, node):\n",
    "        head = 0\n",
    "        tail = len(self.queue) - 1\n",
    "        if tail == -1 or self.compareNode(node, self.queue[tail]) >= 0:\n",
    "            self.queue.append(node)\n",
    "            return\n",
    "        elif self.compareNode(node, self.queue[head]) <= 0:\n",
    "            self.queue = [node] + self.queue\n",
    "            return\n",
    "        while tail - head > 1:\n",
    "            cursor = math.ceil((tail - head) / 2) + head\n",
    "            if self.compareNode(node, self.queue[cursor]) >= 0:\n",
    "                head = cursor\n",
    "            else:\n",
    "                tail = cursor\n",
    "        self.queue = self.queue[:tail] + [node] + self.queue[tail:]\n",
    "\n",
    "    def rebuildQueue(self):\n",
    "        pending = self.pending\n",
    "        self.pending = []\n",
    "        rebuild = False\n",
    "        for num in pending:\n",
    "            if self.updateQueueIfNodeInMaxGap(num):\n",
    "                rebuild = True\n",
    "        if rebuild:\n",
    "            self.rebuildQueue()\n",
    "        \n",
    "    def compareNode(self, a, b):\n",
    "        ga = a['v'] - a['l']['v']\n",
    "        gb = b['v'] - b['l']['v']\n",
    "        if ga > gb:\n",
    "            return 1\n",
    "        elif ga < gb:\n",
    "            return -1\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "    def printQueue(self):\n",
    "        queue = []\n",
    "        for node in self.queue:\n",
    "            queue.append(node['v'])\n",
    "        print(queue)\n",
    "\n",
    "    def findAnswer(self, ans, input):\n",
    "        for v in input:\n",
    "            if (v + ans) in input :\n",
    "                print(v, v + ans)\n",
    "            if (v - ans) in input:\n",
    "                print(v, v - ans)\n",
    "\n",
    "    def createNode(self, val, left = None, right = None):\n",
    "        return {\n",
    "            'v': val,\n",
    "            'l': left,\n",
    "            'r': right,\n",
    "        }\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: 'list[int]') -> 'int':\n",
    "        if len(nums) < 2:\n",
    "            return 0\n",
    "\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            nums[i] = nums[i] - nums[i-1]\n",
    "\n",
    "        max = nums[1]\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] > max:\n",
    "                max = nums[i]\n",
    "\n",
    "        return max\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        l=len(nums)-1\n",
    "        if len(nums)<2:\n",
    "            return 0\n",
    "        while l>0:\n",
    "            nums[l]-=nums[l-1]\n",
    "            l-=1\n",
    "        #for i in range(1,len(nums)):\n",
    "        #    nums[i]=nums[i]-nums[i-1]\n",
    "        print(nums[1:])\n",
    "        return max(nums[1:])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        size = len(nums)\n",
    "        if size < 2: return 0\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for i in range(1, size):\n",
    "            if nums[i] - nums[i - 1] > res: res = nums[i] - nums[i - 1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 2:\n",
    "            return 0\n",
    "        jianju = 0\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)-1):\n",
    "            jianju = max(nums[i+1]-nums[i], jianju)\n",
    "        return jianju"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n<2: return 0\n",
    "        maxnum,minnum = max(nums),min(nums)\n",
    "        if maxnum==minnum: return 0\n",
    "        bucket_len = max(1,(maxnum-minnum)//(n-1))\n",
    "        bucket_num = (maxnum-minnum)//bucket_len+1\n",
    "        buckets = [[] for _ in range(bucket_num)]\n",
    "           \n",
    "        for num in nums:\n",
    "            idx = (num-minnum)//bucket_len\n",
    "            buckets[idx].append(num)\n",
    "\n",
    "        res = 0\n",
    "        pre = float('inf')\n",
    "        for i in range(bucket_num):\n",
    "            if buckets[i]:\n",
    "                res =  max(res,min(buckets[i])-pre)\n",
    "                pre = max(buckets[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        if len(nums) < 2:\n",
    "            return res\n",
    "        sort_nums = sorted(nums)\n",
    "        for cur in range(len(sort_nums) - 1):\n",
    "            next = cur + 1\n",
    "            res = max(res, sort_nums[next] - sort_nums[cur])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if len(nums)<2: return 0\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            res = max(res, nums[i]-nums[i-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        # 基排序\n",
    "        digits=10\n",
    "        length=len(nums)\n",
    "        if length <=1:\n",
    "            return 0\n",
    "        minValue= min(nums)\n",
    "        nums=[num-minValue for num in nums]\n",
    "        buckets=[[] for _ in range(10)]\n",
    "\n",
    "        for digit in range(1,11):\n",
    "            # print('digit',digit)\n",
    "            for num in nums:\n",
    "                digitNum = self.getDigits(num,digit)\n",
    "                # print('digitNum',digitNum)\n",
    "                buckets[digitNum].append(num)\n",
    "            cnt=0\n",
    "            for i in range(10):\n",
    "                while buckets[i] != []:\n",
    "                    number=buckets[i].pop(0)\n",
    "                    nums[cnt]=number\n",
    "                    cnt +=1\n",
    "\n",
    "            # print('nums',nums)\n",
    "\n",
    "        interval=0\n",
    "        for i in range(length-1):\n",
    "            if nums[i+1]-nums[i] >interval:\n",
    "                interval = nums[i+1]-nums[i]\n",
    "        return interval\n",
    "\n",
    "\n",
    "    def getDigits(self,num,i):\n",
    "        return (num- (num//(10**i)) * 10**i)//10**(i-1)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums ) -> int:\n",
    "\n",
    "        if len(nums)<2:\n",
    "            return 0\n",
    "\n",
    "        min_val = float('inf')\n",
    "        max_val = float('-inf')\n",
    "\n",
    "        for num in nums:\n",
    "            min_val = min(min_val,num)\n",
    "            max_val = max(max_val,num)\n",
    "\n",
    "        d = int((max_val-min_val)/(len(nums)-1))\n",
    "        if d == 0:\n",
    "            if max_val-min_val == 0:\n",
    "                return 0\n",
    "            else:\n",
    "                d=1\n",
    "\n",
    "\n",
    "        bucket_num = int((max_val-min_val)/d)+1\n",
    "\n",
    "        buckets = [[float('inf'),float('-inf')] for i in range(bucket_num)]\n",
    "\n",
    "        for num in nums:\n",
    "            bucket_id = (num-min_val)//d\n",
    "\n",
    "            buckets[bucket_id][0] = min(buckets[bucket_id][0],num)\n",
    "            buckets[bucket_id][1] = max(buckets[bucket_id][1],num)\n",
    "\n",
    "        i = 1\n",
    "        ans = 0\n",
    "        last_max = buckets[0][1]\n",
    "        while i<len(buckets):\n",
    "\n",
    "            while i<len(buckets) and buckets[i][0] == float('inf'):\n",
    "                i+=1\n",
    "\n",
    "            if i<len(buckets):\n",
    "                ans = max(buckets[i][0]-last_max,ans)\n",
    "                last_max = buckets[i][1]\n",
    "                i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def radixSort(self,nums):\n",
    "        arr=[[i,n] for i,n in enumerate(nums)]\n",
    "\n",
    "        while True:\n",
    "            buckets=[[] for i in range(10)]\n",
    "            \n",
    "            count_0=0\n",
    "            for ind,ele in enumerate(arr):\n",
    "                n=ele[1]\n",
    "                base=n%10\n",
    "                n=n//10\n",
    "                ele[1]=n\n",
    "                if n==0 :\n",
    "                    count_0+=1\n",
    "                buckets[base].append(ele)\n",
    "            \n",
    "            tmp=[]\n",
    "            for b in buckets:\n",
    "                tmp.extend(b)\n",
    "            arr=tmp\n",
    "\n",
    "            if count_0 == len(nums):\n",
    "                break\n",
    "        sorted_indx= [ind for ind,n in arr]\n",
    "        sorted_nums = [nums[ind] for ind in sorted_indx] \n",
    "        return sorted_nums\n",
    "    \n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        nums= self.radixSort(nums)\n",
    "\n",
    "        max_gap=0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]-nums[i-1]>max_gap:\n",
    "                max_gap = nums[i]-nums[i-1]\n",
    "        return max_gap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 2: return 0\n",
    "        if len(nums) == 2: return abs(nums[0] - nums[1])\n",
    "\n",
    "        # low16 = lambda x: x % 65536\n",
    "        # high16 = lambda x: x // 65536\n",
    "        \n",
    "        cnt = [0] * 65536\n",
    "        tmp = [0] * len(nums)\n",
    "        for x in nums: cnt[x % 65536] += 1\n",
    "        for i in range(1, 65536): cnt[i] += cnt[i - 1]\n",
    "        target = nums[::-1]\n",
    "        for x in target:\n",
    "            data = x % 65536\n",
    "            cnt[data] -= 1\n",
    "            tmp[cnt[data]] = x\n",
    "\n",
    "        cnt = [0] * 65536\n",
    "        for x in tmp: \n",
    "            cnt[x // 65536] += 1\n",
    "        for i in range(1, 65536): cnt[i] += cnt[i - 1]\n",
    "        target = tmp[::-1]\n",
    "        for x in target:\n",
    "            data = x // 65536\n",
    "            cnt[data] -= 1\n",
    "            nums[cnt[data]] = x\n",
    "\n",
    "        maxDist  = -1\n",
    "        for i in range(1, len(nums)):\n",
    "            maxDist = max(maxDist, nums[i]- nums[i-1])\n",
    "        return maxDist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 2: return 0\n",
    "        if len(nums) == 2: return abs(nums[0] - nums[1])\n",
    "\n",
    "        # low16 = lambda x: x % 65536\n",
    "        # high16 = lambda x: x // 65536\n",
    "        \n",
    "        cnt = [0] * 65536\n",
    "        tmp = [0] * len(nums)\n",
    "        for x in nums: cnt[x % 65536] += 1\n",
    "        for i in range(1, 65536): cnt[i] += cnt[i - 1]\n",
    "        target = nums[::-1]\n",
    "        for x in target:\n",
    "            data = x % 65536\n",
    "            cnt[data] -= 1\n",
    "            tmp[cnt[data]] = x\n",
    "\n",
    "        cnt = [0] * 65536\n",
    "        for x in tmp: \n",
    "            cnt[x // 65536] += 1\n",
    "        for i in range(1, 65536): cnt[i] += cnt[i - 1]\n",
    "        target = tmp[::-1]\n",
    "        for x in target:\n",
    "            data = x // 65536\n",
    "            cnt[data] -= 1\n",
    "            nums[cnt[data]] = x\n",
    "\n",
    "        maxDist  = -1\n",
    "        for i in range(1, len(nums)):\n",
    "            if maxDist > nums[i] - nums[i - 1]: continue\n",
    "            maxDist = nums[i]- nums[i-1]\n",
    "        return maxDist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from functools import reduce\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if len(nums)<2:\n",
    "            return 0\n",
    "        nums = list(map(lambda x:list(str(x).rjust(32,'0')),nums))\n",
    "\n",
    "        def sorted_(nums,idx):\n",
    "            bu = [[] for _ in range(10)]\n",
    "            for i in range(len(nums)):\n",
    "                bu[ord(nums[i][idx])-ord('0')].append(i)\n",
    "            res = []\n",
    "            for i in range(10):\n",
    "                for j in range(len(bu[i])):\n",
    "                    res.append(nums[bu[i][j]])\n",
    "            return res\n",
    "        for i in range(31,-1,-1):\n",
    "            nums = sorted_(nums, i)\n",
    "\n",
    "        new_nums = []\n",
    "        for t in nums:\n",
    "            new_nums.append(reduce(lambda x,y:int(x)*10+int(y),t))\n",
    "        res = new_nums[1]-new_nums[0]\n",
    "        for i in range(1,len(new_nums)):\n",
    "            res = max(res,new_nums[i]-new_nums[i-1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bruteForce(self, nums):\n",
    "        nums.sort()\n",
    "        maxGap = 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            maxGap = max(maxGap, nums[i + 1] - nums[i])\n",
    "        return maxGap\n",
    "\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        input length 1? -> output 0\n",
    "        input length 0? -> output 0\n",
    "        '''\n",
    "        if len(nums) < 2:\n",
    "            return 0\n",
    "        numsRange = max(nums) - min(nums) + 1\n",
    "        if numsRange > 1000000:\n",
    "            return self.bruteForce(nums)\n",
    "        offset = min(nums)\n",
    "        existNums = [False for i in range(numsRange)]\n",
    "        for i in range(len(nums)):\n",
    "            existNums[nums[i] - offset] = True\n",
    "        maxDistance = 0\n",
    "        lastExistNumIndex = 0\n",
    "        for i in range(numsRange):\n",
    "            if existNums[i]:\n",
    "                maxDistance = max(i - lastExistNumIndex, maxDistance)\n",
    "                lastExistNumIndex = i\n",
    "        return maxDistance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if (n<2):\n",
    "            return 0\n",
    "        maxnum=max(nums)+1\n",
    "        if n<25 or maxnum>99999900:\n",
    "            nums.sort()\n",
    "            diff=[nums[i]-nums[i-1] for i in range(1,n)]\n",
    "            return max(diff)\n",
    "        sortplace=[0]*maxnum\n",
    "        for i in nums:\n",
    "            if sortplace[i]!=1:\n",
    "                sortplace[i]=1\n",
    "        nsorted=[i for i in range(maxnum) if sortplace[i]!=0]\n",
    "        n2=len(nsorted)\n",
    "        diff=[nsorted[i]-nsorted[i-1] for i in range(1,n2)]\n",
    "        return max(diff)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 2: return 0\n",
    "        heapq.heapify(nums)\n",
    "        ans = 0\n",
    "        pre = heapq.heappop(nums)\n",
    "        while nums:\n",
    "            cur = heapq.heappop(nums)\n",
    "            ans = max(cur - pre, ans)\n",
    "            pre = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 2:\n",
    "            return 0\n",
    "        heapify(nums)\n",
    "        former = heappop(nums)\n",
    "        max_gap = 0\n",
    "        while nums:\n",
    "            latter = heappop(nums)\n",
    "            max_gap = max(max_gap, latter-former)\n",
    "            former = latter\n",
    "        return max_gap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "\n",
    "        pre = None\n",
    "\n",
    "        heapq.heapify(nums)\n",
    "        res = 0\n",
    "        length = len(nums)\n",
    "        for _ in range(length):\n",
    "            q = heapq.heappop(nums)\n",
    "            if pre is not None:\n",
    "                res = max(res, q - pre)\n",
    "            pre = q\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        t = sorted(nums)\n",
    "        return max(y-x for x, y in zip(t, t[1:])) if len(nums) >= 2 else 0 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxD = 10**9\r\n",
    "class Solution:\r\n",
    "    def traverse(self, nums, left , right):\r\n",
    "        key = nums[left]\r\n",
    "        bl = kl = left\r\n",
    "        left+=1\r\n",
    "        minL = maxD\r\n",
    "        minR = maxD\r\n",
    "        while left<right:\r\n",
    "            d = key-nums[left]\r\n",
    "            if d > 0:\r\n",
    "                minL = min(minL, key-nums[left])\r\n",
    "                nums[kl], nums[left] = nums[left], nums[kl+1]\r\n",
    "                kl+=1\r\n",
    "            elif d == 0:\r\n",
    "                right-=1\r\n",
    "                nums[right], nums[left] = nums[left], nums[right]\r\n",
    "                left-=1\r\n",
    "            else:\r\n",
    "                minR = min(minR, -d)\r\n",
    "            left+=1\r\n",
    "        minL = max(minL if minL != maxD else 0, self.traverse(nums, bl, kl) if kl>bl+1 else 0)\r\n",
    "        minR = max(minR if minR != maxD else 0, self.traverse(nums, kl+1, right) if right>kl+2 else 0)\r\n",
    "        return max(minL, minR)\r\n",
    "    def maximumGap(self, nums: List[int]) -> int:\r\n",
    "        if len(nums) <= 1: return 0\r\n",
    "        return self.traverse(nums, 0, len(nums))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        # 方式1，用基数排序，在最后一轮的时候计算最大间距值\n",
    "        if len(nums) < 2:\n",
    "            return 0\n",
    "        res = 0\n",
    "        import math\n",
    "        i, it = 0, int(math.log(max(nums), 10))\n",
    "        while i <= it:\n",
    "            # 生成10个桶\n",
    "            buckets = [[] for _ in range(10)]\n",
    "            for num in nums:\n",
    "                # 分别从个位，十位，百位....开始取余计算\n",
    "                digit = (num // 10 ** i) % 10\n",
    "                # 如果是最后一轮，则计算间距差\n",
    "                if i == it and buckets[digit]:\n",
    "                    res = max(res, num - buckets[digit][-1])\n",
    "                    # 分桶\n",
    "                buckets[digit].append(num)\n",
    "\n",
    "            # 分桶完成，将数据依次取出\n",
    "            nums.clear()\n",
    "            for buc in buckets:\n",
    "                # 最后一轮计算桶边界差\n",
    "                if i == it and nums and buc:\n",
    "                    res = max(res, buc[0] - nums[-1])\n",
    "                # 将数据重新写回nums\n",
    "                nums.extend(buc)\n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maximumGap(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums)<2:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        if nums[0]==nums[-1]:\n",
    "            return 0\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            if i==0:\n",
    "                continue\n",
    "            nums[i]-=nums[i-1]\n",
    "        return max(nums[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if len(nums) <2:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        cha=0\n",
    "        for i in range(len(nums)-1):\n",
    "            print(nums[i])\n",
    "            cha=max(cha,abs(nums[i]-nums[i+1]))\n",
    "        return cha"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            res = max(res, abs(nums[i-1]-nums[i]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if not nums:  # 处理输入为空的情况\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        p = 0\n",
    "        while p < len(nums)-1:\n",
    "            q = p+1\n",
    "            res.append(nums[q]-nums[p])\n",
    "            p += 1\n",
    "        if not res:  # 处理无间距的情况\n",
    "            return 0\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "            if len(nums)<2:\n",
    "                return 0\n",
    "            else:\n",
    "                nums.sort()\n",
    "                a=[]\n",
    "                for i in range(len(nums)):\n",
    "                    if i+1<len(nums):\n",
    "                        a.append(nums[i+1]-nums[i])\n",
    "                return (max(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        \n",
    "        maxn = max(nums)\n",
    "        minn = min(nums)\n",
    "        n = len(nums)\n",
    "        if n==1:\n",
    "            return 0 \n",
    "\n",
    "        d = (maxn-minn)//(n-1)\n",
    "        if d==0:\n",
    "            d = 1 \n",
    "        x = ((maxn-minn)//d )+1\n",
    "        max_bucket = [float(\"-inf\")]*x\n",
    "        min_bucket = [float(\"inf\")]*x \n",
    "\n",
    "        for y in nums:\n",
    "            index = (y-minn)//d \n",
    "            if y>max_bucket[index]:\n",
    "                max_bucket[index] = y \n",
    "            if y<min_bucket[index]:\n",
    "                min_bucket[index] = y \n",
    "\n",
    "        #print(max_bucket)\n",
    "        #print(min_bucket)\n",
    "        pre_max = float(\"inf\")\n",
    "        pre_min = float(\"-inf\")\n",
    "        ans = 0\n",
    "        for i in range(x):\n",
    "            if max_bucket[i]==float(\"-inf\"):\n",
    "                continue\n",
    "            cur_max = max_bucket[i]\n",
    "            cur_min = min_bucket[i]\n",
    "            ans = max(ans,cur_max-cur_min)\n",
    "            ans = max(ans,cur_min-pre_max)\n",
    "            pre_max,pre_min = cur_max,cur_min\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if len(nums)<2: return 0\n",
    "        if len(nums)==2: return abs(nums[0]-nums[1])\n",
    "\n",
    "        minnum = min(nums)\n",
    "        maxnum = max(nums)\n",
    "        if maxnum==minnum: return 0\n",
    "\n",
    "        length = len(nums)+1 #桶的大小\n",
    "        record_max = [-1]*length #记录当前桶的最大值\n",
    "        record_min = [10**6]*length #记录当前桶的最大值\n",
    "        hasnum = [False]*length #记录当前桶是否有数值\n",
    "        for i in range(len(nums)):\n",
    "            idx = int((nums[i]-minnum)*len(nums)/(maxnum-minnum)) #桶的索引\n",
    "            if not hasnum[idx]:\n",
    "                record_max[idx] = nums[i]\n",
    "                record_min[idx] = nums[i]\n",
    "                hasnum[idx] = True\n",
    "            else:\n",
    "                record_max[idx] = max(record_max[idx], nums[i])\n",
    "                record_min[idx] = min(record_min[idx], nums[i])\n",
    "                \n",
    "        res = 0\n",
    "        tmp = record_max[0]\n",
    "        for i in range(1, length):\n",
    "            if hasnum[i]:\n",
    "                res = max(res, record_min[i]-tmp)\n",
    "                tmp = record_max[i]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        \n",
    "        checkList = defaultdict()\n",
    "        buffer = [-1 for _ in range(n)]\n",
    "        maxVal = max(nums)\n",
    "        limit = 1\n",
    "\n",
    "        while maxVal >= limit:\n",
    "            count = [0 for _ in range(10)]\n",
    "            for num in nums:\n",
    "                digit = (num // limit) % 10\n",
    "                count[digit] += 1\n",
    "            \n",
    "            for i in range(1, 10):\n",
    "                count[i] += count[i - 1]\n",
    "\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                digit = (nums[i] // limit) % 10\n",
    "                buffer[count[digit] - 1] = nums[i]\n",
    "                count[digit] -= 1\n",
    "            \n",
    "            nums = buffer[:]\n",
    "            limit *= 10\n",
    "\n",
    "        print(nums)\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            ans = max(ans, nums[i] - nums[i - 1])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 2:\n",
    "            return 0\n",
    "        n = len(str(max(nums)))\n",
    "        for k in range(n):\n",
    "            bucket_list = [[] for _ in range(10)]\n",
    "            for i in nums:\n",
    "                bucket_list[i // (10 ** k) % 10].append(i)\n",
    "            nums = [j for i in bucket_list for j in i]\n",
    "        res = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            res = max(nums[i] - nums[i-1], res)\n",
    "        return res\n",
    "        # if len(nums) < 2:\n",
    "        #     return 0\n",
    "        # n = len(nums)\n",
    "        # min_val = min(nums)\n",
    "        # max_val = max(nums)\n",
    "        # d = max(1, (max_val - min_val) // (n - 1))\n",
    "        # num_buckets = (max_val - min_val) // d + 1\n",
    "        # buckets = [[] for _ in range(num_buckets)]\n",
    "        # for i in nums:\n",
    "        #     buckets_index = (i - min_val) // d\n",
    "        #     tmp = buckets[buckets_index]\n",
    "        #     if len(tmp) == 0:\n",
    "        #         tmp = [i, i]\n",
    "        #     else:\n",
    "        #         tmp = [min(tmp[0], i), max(tmp[1], i)]\n",
    "        #     buckets[buckets_index] = tmp\n",
    "        \n",
    "        # res = 0\n",
    "        # pre = -1\n",
    "        # for i in range(len(buckets)):\n",
    "        #     if len(buckets[i]) > 0:\n",
    "        #         if pre >= 0:\n",
    "        #             res = max(res, buckets[i][0] - buckets[pre][1])\n",
    "        #         pre = i\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if len(nums)<2: return 0\n",
    "        if len(nums)==2: return abs(nums[0]-nums[1])\n",
    "\n",
    "        minnum = min(nums)\n",
    "        maxnum = max(nums)\n",
    "        if maxnum==minnum: return 0\n",
    "\n",
    "        lenth = len(nums)+1 #桶的数量\n",
    "        record_max = [-1]*lenth #记录当前桶的最大值\n",
    "        record_min = [10**6]*lenth #记录当前桶的最大值\n",
    "        hasnum = [False]*lenth #记录当前桶是否有数值\n",
    "        for i in range(len(nums)):\n",
    "            idx = int((nums[i]-minnum)*len(nums)/(maxnum-minnum)) #桶的索引\n",
    "            if not hasnum[idx]:\n",
    "                record_max[idx] = nums[i]\n",
    "                record_min[idx] = nums[i]\n",
    "                hasnum[idx] = True\n",
    "            else:\n",
    "                record_max[idx] = max(record_max[idx], nums[i])\n",
    "                record_min[idx] = min(record_min[idx], nums[i])\n",
    "\n",
    "        print(record_max, record_min, hasnum)\n",
    "        \n",
    "        #  这里计算每个桶之间的差值的最大值，即为最终的最大值\n",
    "        res = 0\n",
    "        tmp = record_max[0] # 第0个桶的最大值\n",
    "        for i in range(1,lenth):\n",
    "            if hasnum[i]:\n",
    "                res = max(res, record_min[i]-tmp) # 计算res与两个桶之间的差值，取最大值；\n",
    "                tmp = record_max[i]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if len(nums)<2:\n",
    "            return 0\n",
    "        if len(nums)==2:\n",
    "            return abs(nums[1]-nums[0])\n",
    "\n",
    "        minimum = min(nums)\n",
    "        maximum = max(nums)\n",
    "        if minimum==maximum:\n",
    "            return 0\n",
    "\n",
    "        N = len(nums)-1\n",
    "        interval = (maximum - minimum)/N\n",
    "\n",
    "        minimums = [float('inf')]*N\n",
    "        maximums = [float('-inf')]*N\n",
    "        \n",
    "        for x in nums:\n",
    "            index = int((x-minimum)/interval)\n",
    "            if index==N:\n",
    "                index=N-1\n",
    "            minimums[index] = min(minimums[index], x)\n",
    "            maximums[index] = max(maximums[index], x)\n",
    "        \n",
    "        minimums = [x for x in minimums if x != float('inf')]\n",
    "        maximums = [x for x in maximums if x != float('-inf')]\n",
    "\n",
    "        result = 0\n",
    "        for i in range(len(minimums)-1):\n",
    "            result = max(result, minimums[i+1]-maximums[i])\n",
    "        \n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        def quickSort(nums):\n",
    "            n=len(nums)\n",
    "            if n<=1:\n",
    "                return nums\n",
    "            pivot_index=random.randint(0, n-1)\n",
    "            pivot=nums[pivot_index]\n",
    "            left_part=[x for x in nums if x < pivot]\n",
    "            mid_part=[x for x in nums if x == pivot]\n",
    "            right_part=[x for x in nums if x > pivot]\n",
    "            return quickSort(left_part)+mid_part+quickSort(right_part)\n",
    "\n",
    "        if len(nums)<2:\n",
    "            return 0\n",
    "        nums=quickSort(nums)\n",
    "        nums1=nums[1:]\n",
    "        nums2=nums[:-1]\n",
    "        results=[]\n",
    "        \n",
    "        for v1,v2 in zip(nums1,nums2):\n",
    "            results.append(v1-v2)\n",
    "        return max(results)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        min_num, max_num = min(nums), max(nums)\n",
    "        bucket_size = max(1, (max_num - min_num) // len(nums) -1)\n",
    "        bucket_num = (max_num - min_num) // bucket_size + 1\n",
    "\n",
    "        buckets = [[None, None] for _ in range(bucket_num)]\n",
    "\n",
    "        for num in nums:\n",
    "            idx  = (num-min_num) // bucket_size\n",
    "            if buckets[idx][0] is None:\n",
    "                buckets[idx][0], buckets[idx][1] = num, num\n",
    "            else:\n",
    "                buckets[idx][0] = min(num, buckets[idx][0])\n",
    "                buckets[idx][1] = max(num, buckets[idx][1])\n",
    "        \n",
    "        max_gap, prev_max = 0, min_num\n",
    "        for i in range(bucket_num):\n",
    "            if buckets[i][0] is not None:\n",
    "                max_gap = max(max_gap, buckets[i][0] - prev_max)\n",
    "                prev_max = buckets[i][1]\n",
    "\n",
    "        return max_gap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        minVal = min(nums)\n",
    "        maxVal = max(nums)\n",
    "        d = max(1, (maxVal - minVal) // (n - 1))\n",
    "        bucketSize = (maxVal - minVal) // d + 1\n",
    "\n",
    "        # 使用 (-1, -1) 初始化 bucket，表示该桶为空\n",
    "        bucket = [[-1, -1] for _ in range(bucketSize)]\n",
    "        \n",
    "        for num in nums:\n",
    "            idx = (num - minVal) // d\n",
    "            if bucket[idx][0] == -1:\n",
    "                bucket[idx][0] = bucket[idx][1] = num\n",
    "            else:\n",
    "                bucket[idx][0] = min(bucket[idx][0], num)\n",
    "                bucket[idx][1] = max(bucket[idx][1], num)\n",
    "\n",
    "        ret = 0\n",
    "        prev = -1\n",
    "        for i in range(bucketSize):\n",
    "            if bucket[i][0] == -1:\n",
    "                continue\n",
    "            if prev != -1:\n",
    "                ret = max(ret, bucket[i][0] - bucket[prev][1])\n",
    "            prev = i\n",
    "            \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 2: return 0\n",
    "        \n",
    "        # 一些初始化\n",
    "        max_ = max(nums)\n",
    "        min_ = min(nums)\n",
    "        max_gap = 0\n",
    "        \n",
    "        each_bucket_len = max(1,(max_-min_) // (len(nums)-1))\n",
    "        buckets =[[] for _ in range((max_-min_) // each_bucket_len + 1)]\n",
    "        \n",
    "        # 把数字放入桶中\n",
    "        for i in range(len(nums)):\n",
    "            loc = (nums[i] - min_) // each_bucket_len\n",
    "            buckets[loc].append(nums[i])\n",
    "        \n",
    "        # 遍历桶更新答案\n",
    "        prev_max = float('inf')\n",
    "        for i in range(len(buckets)):\n",
    "            if buckets[i] and prev_max != float('inf'):\n",
    "                max_gap = max(max_gap, min(buckets[i])-prev_max)\n",
    "            \n",
    "            if buckets[i]:\n",
    "                prev_max = max(buckets[i])\n",
    "                \n",
    "        return max_gap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 2:\n",
    "            return 0 \n",
    "        \n",
    "        max_ = max(nums)\n",
    "        min_ = min(nums)\n",
    "        max_gap = 0 \n",
    "        print(max(1, (max_ - min_)),len(nums),12)\n",
    "        each_bucket_len = max(1, (max_ - min_) // (len(nums) - 1))\n",
    "        buckets =[[] for _ in range((max_ - min_) // each_bucket_len + 1)]\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            loc = (nums[i] - min_) // each_bucket_len\n",
    "            buckets[loc].append(nums[i])\n",
    "\n",
    "        prev_max = float('inf')\n",
    "        for i in range(len(buckets)):\n",
    "            if buckets[i] and prev_max != float('inf'):\n",
    "                max_gap = max(max_gap, min(buckets[i])-prev_max)\n",
    "            \n",
    "            if buckets[i]:\n",
    "                prev_max = max(buckets[i])\n",
    "        return max_gap\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 2: return 0\n",
    "\n",
    "        min_ = min(nums)\n",
    "        max_ = max(nums)\n",
    "\n",
    "        bottle_size = max(1, (max_ - min_)//(len(nums) - 1))\n",
    "        bottles = [[] for _ in range((max_ - min_)//bottle_size + 1)]\n",
    "\n",
    "        for i in nums:\n",
    "            bottles[(i - min_)//bottle_size].append(i)\n",
    "\n",
    "        last = max(bottles[0])\n",
    "        res = 0\n",
    "        for b in bottles[1:]:\n",
    "            if b:\n",
    "                res = max(res, min(b) - last) \n",
    "                last = max(b)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bucket_sort(self, arr):\n",
    "        # 创建空桶\n",
    "        num_buckets = len(arr)\n",
    "        buckets = [[] for _ in range(num_buckets)]\n",
    "\n",
    "        # 将元素分配到桶中\n",
    "        max_val = max(arr)\n",
    "        for num in arr:\n",
    "            index = int(num * num_buckets / (max_val + 1))\n",
    "            buckets[index].append(num)\n",
    "\n",
    "        # 对每个桶内的元素进行排序（这里使用插入排序）\n",
    "        for i in range(num_buckets):\n",
    "            buckets[i].sort()\n",
    "\n",
    "        # 合并排序后的桶\n",
    "        result = []\n",
    "        for bucket in buckets:\n",
    "            result.extend(bucket)\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        sorted_nums = self.bucket_sort(nums)\n",
    "        max_gap = 0\n",
    "        for i in range(len(sorted_nums)-1):\n",
    "            max_gap = max(max_gap, sorted_nums[i+1]-sorted_nums[i])\n",
    "        return max_gap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n<2:\n",
    "            return 0\n",
    "        \n",
    "        maxNum = max(nums)\n",
    "        minNum = min(nums)\n",
    "        max_gap=0\n",
    "\n",
    "        each_bucket_len=max(1,(maxNum-minNum)//(len(nums)-1))\n",
    "        buckets =[[] for _ in range((maxNum-minNum) // each_bucket_len + 1)]\n",
    "\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            loc = (nums[i] - minNum) // each_bucket_len\n",
    "            buckets[loc].append(nums[i])\n",
    "        print(buckets)\n",
    "\n",
    "        prev_max=float(\"inf\")\n",
    "        for i in range(len(buckets)):\n",
    "            if buckets[i] and prev_max!=float(\"inf\"):\n",
    "                max_gap=max(max_gap, min(buckets[i])-prev_max)\n",
    "            \n",
    "            if buckets[i]:\n",
    "                prev_max=max(buckets[i])\n",
    "        return max_gap\n",
    "\n",
    "\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        # def maximumGap(nums):\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return 0\n",
    "\n",
    "        # 计算桶的数量和区间大小\n",
    "        min_val, max_val = min(nums), max(nums)\n",
    "        gap = max(1, (max_val - min_val) // (n - 1))\n",
    "        num_buckets = (max_val - min_val) // gap + 1\n",
    "\n",
    "        # 初始化桶和记录每个桶的最大值和最小值\n",
    "        buckets = [[] for _ in range(num_buckets)]\n",
    "        for num in nums:\n",
    "            idx = (num - min_val) // gap\n",
    "            buckets[idx].append(num)\n",
    "\n",
    "        bucket_min = [min(b) for b in buckets if b]\n",
    "        bucket_max = [max(b) for b in buckets if b]\n",
    "\n",
    "        # 计算相邻非空桶之间的最大差值\n",
    "        max_gap = 0\n",
    "        for i in range(1, len(bucket_min)):\n",
    "            max_gap = max(max_gap, bucket_min[i] - bucket_max[i-1])\n",
    "        \n",
    "        return max_gap\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "###桶排序，因为最大间隔>=(max-min)//(len(num1)-1),否则max=min+(len-1)*间隔<min+(max-min)/(len-1)*(len-1)=max矛盾，想设计桶使得桶内元素间隔<max-min//(len-1),那么最大间隔只产生在桶之间。假设分桶原则为index=num//b,同一个桶的元素满足i<=index<i+1,即i*b=<num<(i+1)*b,所以想让桶内元素间隔<b<(max-min)//(len-1),b=(max-min)/len满足条件，因为分桶index>0,元素可能小于0，所以减去一个最小值。因此分桶规则为(i-min)*len/(max-min)，min在0桶，max在len桶，桶个数为len+1\n",
    "         \n",
    "        bucket=[[] for _ in range(len(nums)+1)]\n",
    "        min1=min(nums)\n",
    "        max1=max(nums)\n",
    "        maxbuc=[-float('inf')]*(len(nums)+1)\n",
    "        minbuc=[float('inf')]*(len(nums)+1)\n",
    "        hasnum=[False]*(len(nums)+1)\n",
    "        if len(nums)<=2:\n",
    "            return max1-min1\n",
    "        if max1==min1:\n",
    "            return 0\n",
    "        for n in nums:\n",
    "            index=(n-min1)*len(nums)//(max1-min1)\n",
    "            bucket[index].append(n)\n",
    "            maxbuc[index]=max(maxbuc[index],n)\n",
    "            minbuc[index]=min(minbuc[index],n)\n",
    "            hasnum[index]=True\n",
    "        maxdis=-float('inf')\n",
    "        #print(maxbuc,minbuc)\n",
    "        maxnum=maxbuc[0]###记录不为空的桶的最大值，间隔为不为空桶的最小值-前一个桶最大值,第0个桶一定有数字min1,hasnum[0]=True\n",
    "        for i in range(1,len(nums)+1):\n",
    "            if hasnum[i]:\n",
    "                maxdis=max(maxdis,minbuc[i]-maxnum)\n",
    "                maxnum=maxbuc[i]\n",
    "        return maxdis\n",
    "\n",
    "            \n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n==1: return 0\n",
    "        maxn=max(nums);minn=min(nums)\n",
    "        k=max(1,(maxn-minn)//(n-1))\n",
    "        b=(maxn-minn)//k+1\n",
    "        bucket=[[] for _ in range(b)]\n",
    "        for i in range(n):\n",
    "            loc=(nums[i]-minn)//k\n",
    "            bucket[loc].append(nums[i])\n",
    "        res=0\n",
    "        for i in range(1,b):\n",
    "            if not bucket[i]: bucket[i]=[max(bucket[i-1])]\n",
    "            res=max(min(bucket[i])-max(bucket[i-1]),res)\n",
    "        print(bucket)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import math\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n<2:\n",
    "            return 0\n",
    "        max_num=max(nums)\n",
    "        min_num=min(nums)\n",
    "        d=max(1, (max_num-min_num)//(n-1))\n",
    "        m=(max_num-min_num)//d +1\n",
    "        buckets=[(-math.inf, math.inf, False)]*m\n",
    "        for num in nums:\n",
    "            idx=(num-min_num)//d\n",
    "            if buckets[idx][2]:\n",
    "                buckets[idx]=(min(buckets[idx][0], num), max(buckets[idx][1], num), True)\n",
    "            else:\n",
    "                buckets[idx]=(num, num, True)\n",
    "        ans=0\n",
    "        print(buckets)\n",
    "        for i in range(m-1):\n",
    "            if buckets[i][2]:\n",
    "                j=i+1\n",
    "                while j < m and buckets[j][2]==False:\n",
    "                    j+=1\n",
    "                if buckets[j][2]:\n",
    "                    ans=max(ans, buckets[j][0]-buckets[i][1])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        nums=list(set(nums))\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        mn=min(nums)\n",
    "        mx=max(nums)\n",
    "        if n==2:\n",
    "            return mx-mn\n",
    "        if mx==mn:\n",
    "            return 0\n",
    "        m=(mx-mn+1)//(n-1)\n",
    "        buckets=[[1145141919810,0] for _ in range((mx-mn+m)//m)]\n",
    "        for e in nums:\n",
    "            i=(e-mn)//m \n",
    "            buckets[i][0]=min(buckets[i][0],e)\n",
    "            buckets[i][1]=max(buckets[i][1],e)\n",
    "            # print(i,buckets)\n",
    "        ans=0\n",
    "        i=0\n",
    "        while i < len(buckets)-1:\n",
    "            j=i+1\n",
    "            while buckets[j][0]==1145141919810:\n",
    "                j+=1\n",
    "            ans=max(ans,buckets[j][0]-buckets[i][1])\n",
    "            i=j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n<2:\n",
    "            return 0\n",
    "        maxval,minval=max(nums),min(nums)\n",
    "        d=max(1,(maxval-minval)//(n-1))\n",
    "        bucketsize=(maxval-minval)//d+1\n",
    "        bucket=[[float('inf'),float('-inf')] for _ in range(bucketsize)]\n",
    "        for num in nums:\n",
    "            idx=(num-minval)//d\n",
    "            bucket[idx][0]=min(bucket[idx][0],num)\n",
    "            bucket[idx][1]=max(bucket[idx][1],num)\n",
    "        ans,prev=0,-1\n",
    "        for i in range(bucketsize):\n",
    "            if bucket[i][0]==float('inf') or bucket[i][1]==float('-inf'):\n",
    "                continue\n",
    "            if prev!=-1:\n",
    "                ans=max(ans,bucket[i][0]-bucket[prev][1])\n",
    "            prev=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import math\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n<2:\n",
    "            return 0\n",
    "        max_num=max(nums)\n",
    "        min_num=min(nums)\n",
    "        d=max(1, (max_num-min_num)//(n-1))\n",
    "        m=(max_num-min_num)//d +1\n",
    "        buckets=[[math.inf, -math.inf, False] for _ in range(m)]\n",
    "        for num in nums:\n",
    "            idx=(num-min_num)//d\n",
    "            buckets[idx][2]=True\n",
    "            buckets[idx][0]=min(buckets[idx][0], num)\n",
    "            buckets[idx][1]=max(buckets[idx][1], num)\n",
    "        ans=0\n",
    "        last=min_num\n",
    "        for i in range(m):\n",
    "            if buckets[i][2]:\n",
    "                ans=max(ans, buckets[i][0]-last)\n",
    "                last=buckets[i][1]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        maxNum, minNum = nums[0], nums[0]\n",
    "        for num in nums:\n",
    "            if num > maxNum:\n",
    "                maxNum = num\n",
    "            if num < minNum:\n",
    "                minNum = num\n",
    "        bucketGap = (maxNum - minNum) // (n - 1)\n",
    "        if bucketGap == 0:\n",
    "            bucketGap = 1\n",
    "        bucketMin = {}\n",
    "        bucketMax = {}\n",
    "        for num in nums:\n",
    "            bucketId = (num - minNum) // bucketGap\n",
    "            if bucketId not in bucketMin.keys():\n",
    "                bucketMin[bucketId] = num\n",
    "                bucketMax[bucketId] = num\n",
    "            else:\n",
    "                if num < bucketMin[bucketId]:\n",
    "                    bucketMin[bucketId] = num\n",
    "                if num > bucketMax[bucketId]:\n",
    "                    bucketMax[bucketId] = num\n",
    "        lastMax = bucketMax[0]\n",
    "        ans = 0\n",
    "        for bucketId in range(n):\n",
    "            if bucketId in bucketMin.keys():\n",
    "                if bucketMax[bucketId] - bucketMin[bucketId] > ans:\n",
    "                    ans = bucketMax[bucketId] - bucketMin[bucketId]\n",
    "                if bucketId > 0:\n",
    "                    if bucketMin[bucketId] - lastMax > ans:\n",
    "                        ans = bucketMin[bucketId] - lastMax\n",
    "                    lastMax = bucketMax[bucketId]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 2: \n",
    "            return 0\n",
    "        max_num = max(nums)\n",
    "        min_num = min(nums)\n",
    "\n",
    "        # n个数分到n-1个桶, 不放最大最小值, gap可以设置得更小一点\n",
    "        gap = math.ceil((max_num - min_num) / (n-1))\n",
    "\n",
    "        # 每个bucket维护最小值和最大值\n",
    "        bucket = [[float('inf'), -float('inf')] for i in range(n-1)]\n",
    "        for i in range(n):\n",
    "            if nums[i] == max_num or nums[i] == min_num:\n",
    "                continue\n",
    "            loc = (nums[i] - min_num) // gap\n",
    "            bucket[loc][0] = min(bucket[loc][0], nums[i])\n",
    "            bucket[loc][1] = max(bucket[loc][1], nums[i])\n",
    "        \n",
    "        premin = min_num\n",
    "        res = -float('inf')\n",
    "        for x,y in bucket:\n",
    "            if x == float('inf'):\n",
    "                continue\n",
    "            res = max(res, x - premin)\n",
    "            premin = y\n",
    "        \n",
    "        print(premin, max_num)\n",
    "        res = max(res, max_num - premin)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumGap(self, nums: List[int]) -> int:\n",
    "        n_len = len(nums)\n",
    "        if n_len < 2: return 0\n",
    "        \n",
    "        min_val, max_val = min(nums), max(nums)\n",
    "        d = max(1, (max_val - min_val) // (n_len - 1))\n",
    "        b_len = (max_val - min_val) // d + 1\n",
    "        \n",
    "        buckets = [[float('inf'), float('-inf')] for _ in range(b_len)]\n",
    "        for n in nums:\n",
    "            bk_i = (n - min_val) // d\n",
    "            if n < buckets[bk_i][0]: buckets[bk_i][0] = n\n",
    "            if n > buckets[bk_i][1]: buckets[bk_i][1] = n\n",
    "        \n",
    "        rnt, pre = 0, min_val\n",
    "        for i in range(b_len):\n",
    "            if buckets[i][0] == float('inf'): continue\n",
    "            \n",
    "            rnt = max(rnt, buckets[i][0]-pre)\n",
    "            pre = buckets[i][1]\n",
    "        \n",
    "        return rnt"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
